#ifndef ALGOGRAPH_BN0149RN

#define ALGOGRAPH_BN0149RN


#include <iostream>
#include <set>
#include <vector>
#include <map>


namespace AlgoGraph
{




    namespace // anonymous
    {

        /**
         * @brief
         *
         * @param graph graph
         * @param node current node
         * @param L visited node
         * @param S no visited node
         * @param result ne doit pas etre aloué. output : result[position] = element
         *
         * @return acyclic ? true : false;
         */
        template <class U, class G>
        bool topologicalVisit( G &graph, const U node, std::set<U> &L, std::set<U> &S, std::vector<U> &result ) // TEST : OK
        {
            if( L.count( node ) > 0 )
                return true;

            if( S.count( node ) == 0 )
                return false;

            S.erase( node );

            bool acyclic = true;

            for (typename std::set<U>::iterator it = graph[node].begin(); it != graph[node].end(); ++it)
                if( !topologicalVisit( graph, *it, L, S, result ) )
                    acyclic = false;

            result.push_back(node);
            L.insert(node);
            return acyclic;
        }

        /**
         * @brief
         *
         * @param graph graph
         * @param node current node
         * @param L visited node
         * @param S no visited node
         *
         * @return acyclic ? true : false;
         */
        template <class U, class G>
        bool existesPath( G &graph, const U node, const U search, std::set<U> &L, std::set<U> &S ) // TEST : OK
        {
            if( L.count( node ) > 0 )
                return false;

            if( S.count( node ) == 0 )
                return false;

            S.erase( node );

            if( node == search )
                return true;

            for (typename std::set<U>::iterator it = graph[node].begin(); it != graph[node].end(); ++it)
                if(existesPath( graph, *it, search, L, S ))
                    return true;

            L.insert(node);
            return false;
        }

    }

    /**
    * @brief reverses a graph
    *
    * @param G-the graph to reverse
    * @param result-the reversed graph
    */
    void reverseGraph( std::vector<std::set<unsigned int> > &G, std::vector<std::set<unsigned int> > &result );


    /**
     * @brief
     *
     * @param graph graphe
     * @param S All node (No visited node)
     * @param result ne doit pas étre aloué. output : result[position] = element
     *
     * @return acyclic ?
     */
    template <class U, class G>
    bool topologicalSorting( G &graph, std::set<U> S, std::vector<U> &result ) // TEST : OK
    {
        bool acyclic = true;

        // sorted
        std::set<U> L;

        while( S.size() > 0 )
            if( topologicalVisit<U, G>( graph, *(S.begin()), L, S, result ) == false )
                acyclic = false;

        return acyclic;
    }

    /**
     * @brief
     *
     * @param graph
     * @param S All node (No visited node)
     * @param noGraph
     * @param result doit etre aloué. result[ element ] = id de la partition
     */
    template <class U, class G, class R>
    unsigned int stronglyConnected( G &graph, std::set<U> S, G &noGraph, R &result ) // TEST : OK
    {
        unsigned int id = 0;
        std::vector<U> r1;
        std::vector<U> r2;

        // sorted
        std::set<U> L;

        topologicalSorting( graph, S, r1 );

        for (int i = r1.size()-1; i >= 0; i--)
        {
            r2.clear();
            topologicalVisit( noGraph, r1[i], L, S, r2 );

            for (unsigned int j = 0; j < r2.size(); j++)
                result[r2[j]] = id;

            if(r2.size() > 0)
                ++id;
        }

        return id;
    }

    template <class U, class G>
    unsigned int stronglyConnected( G &graph, std::set<U> S, std::vector<U> &res, std::vector<std::set<U> > &result ) // TEST : OK
    {
        std::vector<std::set<unsigned int> > reverseG;
        reverseGraph(graph, reverseG);

        res.resize(S.size());
        result.resize(stronglyConnected(graph, S, reverseG, res));
        for ( unsigned int i = 0; i < res.size(); ++i )
        	result[res[i]].insert(i);
        return result.size();
    }

    /**
     * @brief
     *
     * @param graph
     * @param S All node (No visited node)
     * @param result doit étre aloué. result[ element ] = id de la partition
     */
    template <class U, class G, class R>
    void connected( G &graph, std::set<U> S, R &result )
    {
        unsigned id=0;
        std::vector<U> r;

        // sorted
        std::set<U> L;

        while( S.size() > 0 )
        {
            r.clear();
            topologicalVisit( graph, *(S.begin()), L, S, r );
            for (unsigned int i = 0; i < r.size(); i++)
                result[ r[i] ] = id;

            if(r.size() > 0)
                ++id;
        }

    }

    /**
     * @brief this function is testing if a graph is biparti,
     * and also fills graph with the cells contained in each cluster,
     * and fills cells with the corresponding cluster for each cell
     * @param graph - is the graphe we work on
     * @param clusters - the clusters with the cells they contain
     * @param cells - for each cell the cluster
     * @return true if graph is biparti, false otherwise
     */
    bool bipartiGraphClusters( std::vector<std::set<unsigned int> > &graph,
        		std::vector<std::set<unsigned int> > &clusters, std::vector<unsigned int> &cells);

    bool bipartiGraphCluster( std::vector<std::set<unsigned int> > &graph,
    		std::vector<std::set<unsigned int> > &clusters,
    		std::vector<unsigned int> &cells,
    		unsigned int begin, std::vector<int> &visited );


    /**
     * @brief search if exists a path with a -> b
     *
     * @param G graphe
     * @param a begin
     * @param b end
     *
     * @return exists Path ? true : false;
     */
    template <class T>
    bool existsPath( std::vector<std::set<T> > &G, T a, T b) // TEST : OK
    {
        std::set<T> L;
        std::set<T> S;
        std::vector<T> result;
        for (T i = 0; i < G.size(); i++)
            S.insert(i);

        return existesPath( G, a, b, L, S);
    }

    /**
     * @brief search if exists a path with a -> b
     *
     * @param G graphe
     * @param a begin
     * @param b end
     * @param N no use this node for the path
     *
     * @return exists Path ? true : false;
     */
    template <class T>
    bool existsPath( std::vector<std::set<T> > &G, T a, T b, std::set<T> N)
    {
        std::set<T> L;
        std::set<T> S;
        std::vector<T> result;
        for (T i = 0; i < G.size(); i++)
            S.insert(i);
        for (typename std::set<T>::iterator it = N.begin(); it != N.end(); ++it)
        {
            S.erase( *it );
            L.insert( *it );
        }

        return existesPath( G, a, b, L, S);
    }


}



#endif /* end of include guard: ALGOGRAPH_BN0149RN */
